package leetcode_801_900;

import java.util.*;

public class LeeCode_886 {
    public static void main(String[] args) {

    }
    private static boolean possibleBipartition(int n, int[][] dislikes) {
        int[] p = new int[n];
        List<Integer>[] ns = new List[n];
        for (int i = 0; i < n; i++) {
            p[i] = i;
            ns[i] = new ArrayList<>();
        }
        for (int[] dislike : dislikes) {
            ns[dislike[0] - 1].add(dislike[1] - 1);
            ns[dislike[1] - 1].add(dislike[0] - 1);
        }
        for (int i = 0; i < n; i++) {
            for (Integer j : ns[i]) {
                if (find(i, p) == find(j, p)){
                    return false;
                }
                p[find(j, p)] = find(ns[i].get(0), p);
            }
        }
        return true;
    }
    private static int find(int x, int[] p){
        if (p[x] != x){
            p[x] = find(p[x], p);
        }
        return p[x];
    }
}
